#include "IDigraph.h"
#include <vector>
#include <queue>
#include <memory>

IDigraph::~IDigraph() {};

IMatrixGraph::IMatrixGraph(const std::vector<Edge> &edges, int vertices_num)
{
	vertices_num_ = vertices_num;
	matrix_.resize(vertices_num_);
	for (int i = 0; i < vertices_num; i++)
		matrix_[i].resize(vertices_num, false);
	for (size_t i = 0; i < edges.size(); i++)
		matrix_[edges[i].begin][edges[i].end] = true;
}

int IMatrixGraph::getNumberOfVertices() const
{
	return vertices_num_;
}

std::vector<int> IMatrixGraph::getIncidenceList(int vertex) const
{
	std::vector<int> result;
	for (int i = 0; i < vertices_num_; i++)
	if (matrix_[vertex][i]) result.push_back(i);
	return result;
}

bool IMatrixGraph::isEdge(const Edge &edge) const
{
	return matrix_[edge.begin][edge.end];
}

size_t IMatrixGraph::byteSize() const
{
	return sizeof(std::vector< std::vector<bool> >) + sizeof(std::vector<bool>) * matrix_.size() +
		matrix_.size() * matrix_.size() / 8; // assuming that vector<bool> stores its content as bits (not bytes);
}

IListGraph::IListGraph(const std::vector<Edge> &edges, int vertices_num)
{
	vertices_num_ = vertices_num;
	offsets_.resize(vertices_num + 1);
	list_.resize(edges.size());
	for (size_t i = 0; i < edges.size(); i++)
		offsets_[1 + edges[i].begin]++;
	for (int i = 1; i <= vertices_num; i++)
		offsets_[i] += offsets_[i - 1];
	for (size_t i = 0; i < edges.size(); i++)
		list_[offsets_[edges[i].begin]++] = edges[i].end;
	for (int i = vertices_num; i >= 1; i--)
		offsets_[i] = offsets_[i - 1];
	offsets_[0] = 0;
}

int IListGraph::getNumberOfVertices() const
{
	return vertices_num_;
}

std::vector<int> IListGraph::getIncidenceList(int vertex) const
{
	return std::vector<int>(list_.begin() + offsets_[vertex], list_.begin() + offsets_[vertex + 1]);
}

bool IListGraph::isEdge(const Edge &edge) const
{
	for (int i = offsets_[edge.begin]; i < offsets_[edge.begin + 1]; i++)
	if (list_[i] == edge.end) return true;
	return false;
}

size_t IListGraph::byteSize() const
{
	return sizeof(std::vector<int>) * 2 + sizeof(int)* (list_.size() + offsets_.size());
}